0% completed
In this lesson, we’ll explore how to analyze the space requirements of algorithms by looking at two examples. We’ll start with an algorithm that uses constant space
Example 1: Finding the Maximum Element (Constant Space – )
Let’s begin with a simple algorithm to find the maximum element in a list. This algorithm only needs a small, fixed amount of memory, regardless of the input size.
Algorithm Code
Step-by-Step Space Complexity Analysis
-
Input Storage:
- The input array
arrhaselements, where is the length of the list. However, input space is not counted in auxiliary space complexity, so we focus on the additional memory used by the algorithm.
- The input array
-
Auxiliary Space:
- Variable
max_val: We use this variable to store the current maximum value. No matter how largenis, this variable only takes up one unit of memory. - Loop Variable
num: This variable stores each element inarras we iterate through it. Again, this requires only one unit of memory, asnumis overwritten in each iteration.
- Variable
-
Total Space Complexity:
- Since we’re only storing a fixed number of variables (
max_valandnum), the memory required does not increase withn. Therefore, the space complexity is.
- Since we’re only storing a fixed number of variables (
Example 2: Matrix Multiplication (Quadratic Space – )
Now, let’s look at an algorithm for multiplying two matrices. Here, we’ll require memory that grows with the size of the input, leading to a quadratic space complexity.
Algorithm Code
Step-by-Step Space Complexity Analysis
-
Input Storage:
- The matrices
AandBare bothmatrices, so each one requires memory units. But as with the first example, we focus on auxiliary space and ignore the memory used to store inputs.
- The matrices
-
Auxiliary Space:
- Output Matrix
result: The result of multiplying twomatrices is another matrix. We need to create this matrix to store the final product. Since resulthaselements, it takes up memory. - Loop Variables
i,j, andk: These variables are used for iteration and only occupy a fixed amount of memory, which is.
- Output Matrix
-
Total Space Complexity:
- The dominant space usage here is the
resultmatrix, which requiresmemory units. Therefore, the space complexity is .
- The dominant space usage here is the
On this page
Example 1: Finding the Maximum Element (Constant Space –
Example 2: Matrix Multiplication (Quadratic Space –